home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / demos / GL / flip / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  3.4 KB  |  177 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    hash.c
  19.  *    Various functions for figuring out if we've seen
  20.  *    a vertex/edge before.  Uses very simple hashing schemes,
  21.  *  not appropriate for heavy-duty industrial use.
  22.  *  See hash.h for programmer's interface.
  23.  */
  24. #include <stdio.h>
  25. #include "hash.h"
  26.  
  27. typedef struct {
  28.     int v0, v1;    /* Two vertices... */
  29.     int num;    /* And a unique number */
  30. } h_edge;
  31. typedef struct {
  32.     float *v;    /* Pointer to float[3] data */
  33.     int num;    /* And unique number */
  34. } h_vertex;
  35.  
  36. /*
  37.  * The actual hash tables...
  38.  */
  39. static h_vertex *vh = NULL;
  40. static int vsize = 0;
  41. static h_edge *eh = NULL;
  42. static int esize = 0;
  43.  
  44. /*
  45.  * And for consecutive vertex/edge/face numbering
  46.  *    (so each gets his/her/its own number, and we
  47.  *    actually know how many there are at the end)
  48.  */
  49. static int lastv = 0;
  50. static int laste = 0;
  51.  
  52. int
  53. h_get_nv()
  54. {
  55.     return lastv;
  56. }
  57. int
  58. h_get_ne()
  59. {
  60.     return laste;
  61. }
  62.  
  63. /*
  64.  *    Create a hash table for n vertices
  65.  */
  66. void
  67. h_init_vertex(n)
  68. int n;
  69. {
  70.     int i;
  71.  
  72.     vsize = n * 2;
  73.     vh = (h_vertex *) malloc(sizeof(h_vertex) * vsize);
  74.     for (i = 0; i < vsize; i++) vh[i].num = (-1);
  75. }
  76. void h_destroy_vertex()
  77. {
  78.     free(vh);
  79.     lastv = vsize = 0;
  80. }
  81.  
  82. /*
  83.  * Search the hash table for vertex with given xyz.
  84.  *    Return vertex number.
  85.  */
  86. int
  87. h_find_vertex(xyz)
  88. float *xyz;
  89. {
  90.     float d;
  91.     int hpos;
  92.  
  93. /* Starting at the previous entry, go looking for
  94.  *    a vertex close enough to be the same...
  95.  */
  96.     d = (xyz[0] + xyz[1] + xyz[2])*19997.0;    /* Spread out... */
  97.     if (d < 0.0) d = -d;
  98.     hpos = (int)(d) % vsize;
  99.  
  100.     while (vh[hpos].num >= 0) /* Hash position FULL */
  101.     {
  102.         /*
  103.          * So start looking for this vertex in hash list
  104.          */
  105.         if (veq(vh[hpos].v, xyz))
  106.         {
  107.             return vh[hpos].num;
  108.         }
  109.         else hpos = (hpos + 1) % vsize;    /* Check next spot */
  110.     }
  111.     /* If it wasn't found, insert it */
  112.     vh[hpos].num = lastv;
  113.     vh[hpos].v = xyz;
  114.     ++lastv;
  115.     return vh[hpos].num;
  116. }
  117.  
  118. #define FLUFF 1.0e-5
  119. #define ABS(a) ((a) < 0.0 ? -(a) : (a))
  120. #define EQ(a, b) ( ABS((a)-(b)) < FLUFF )
  121.  
  122. int
  123. veq(v0, v1)
  124. float *v0, *v1;
  125. {
  126.     if (EQ(v0[0], v1[0]) && EQ(v0[1], v1[1]) && EQ(v0[2], v1[2]))
  127.             return 1;
  128.     return 0;
  129. }
  130.  
  131. void
  132. h_init_edge(n)
  133. int n;
  134. {
  135.     int i;
  136.     esize = n * 2;
  137.     eh = (h_edge *) malloc(sizeof(h_edge) * esize);
  138.     for (i = 0; i < esize; i++) eh[i].num = (-1);
  139. }
  140. void
  141. h_destroy_edge()
  142. {
  143.     free(eh);
  144.     laste = esize = 0;
  145. }
  146.  
  147. /*
  148.  *    Search hash table for edge defined by v1, v2
  149.  *    Return edge number.
  150.  */
  151. int
  152. h_find_edge(v0, v1)
  153. int v0, v1;
  154. {
  155.     int hpos;
  156.  
  157.     if (v0 > v1)
  158.     {
  159.         int t;
  160.         t = v0; v0 = v1; v1 = t;
  161.     }
  162.     hpos = (v0 * 9997 + v1) % esize;
  163.     while (eh[hpos].num >= 0)
  164.     {
  165.         if ((eh[hpos].v0 == v0) && (eh[hpos].v1 == v1))
  166.         {
  167.             return eh[hpos].num;
  168.         }
  169.         else hpos = (hpos + 1) % esize;
  170.     }
  171.     eh[hpos].num = laste;
  172.     eh[hpos].v0 = v0;
  173.     eh[hpos].v1 = v1;
  174.     ++laste;
  175.     return eh[hpos].num;
  176. }
  177.